package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func kthToLast(head *ListNode, k int) int {
	cache := []int{}
	node := head
	for node != nil {
		cache = append(cache, node.Val)
		node = node.Next
	}
	return cache[len(cache)-k]
}

func getKthFromEnd(head *ListNode, k int) *ListNode {
	cache := []*ListNode{}
	node := head
	for node != nil {
		cache = append(cache, node)
		node = node.Next
	}
	return cache[len(cache)-k]
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func mirrorTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	node := new(TreeNode)
	node.Val = root.Val
	if root.Right != nil {
		node.Left = mirrorTree(root.Right)
	}
	if root.Left != nil {
		node.Right = mirrorTree(root.Left)
	}
	return node
}

/*
从一个有序数组创建出一颗高度平衡的二叉树
*/
func addtoBst(nums []int, s, e int) *TreeNode {
	if e-s < 0 {
		return nil
	}
	node := new(TreeNode)
	middle := s + (e-s)/2
	node.Val = nums[middle]
	if e == s {
		return node
	}
	if e-1 == s {
		right := new(TreeNode)
		right.Val = nums[e]
		node.Right = right
		return node
	}
	left := addtoBst(nums, s, middle-1)
	right := addtoBst(nums, middle+1, e)
	node.Left = left
	node.Right = right
	return node
}

func sortedArrayToBST(nums []int) *TreeNode {
	return addtoBst(nums, 0, len(nums)-1)
}

func main() {
	nums := []int{-10, -3, 0, 5, 9}
	sortedArrayToBST(nums)

	//math.Pow()
}

//func addtoBst(root *TreeNode,)
